package stu.day25_day32.day32;

public class hw2 {

    public int numEnclaves(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int num = 0;

        for(int i=0;i<n;i++){
            for (int j=0;j<m;j++){
                if(i==0||i==n-1||j==0||j==m-1){
                    dfs1(i,j,n,m,grid);
                }
            }
        }

        for(int i=0;i<n;i++){
            for (int j=0;j<m;j++){
                if(grid[i][j]==1){
                   num+=1;
                }
            }
        }

        return num;

    }

    public void dfs1(int i,int j,int n,int m,int[][] grid){
        if(i>=0&&i<n&&j>=0&&j<m){
            if(grid[i][j]==1){
                grid[i][j]=2;
                dfs1(i+1,j,n,m,grid);
                dfs1(i-1,j,n,m,grid);
                dfs1(i,j+1,n,m,grid);
                dfs1(i,j-1,n,m,grid);
            }
        }
    }



    public int numIslands(char[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int num = 0;

        for(int i=0;i<n;i++){
            for (int j=0;j<m;j++){
                if(grid[i][j]=='1'){
                    dfs2(i,j,n,m,grid);
                    num += 1;
                }
            }
        }
        return num;


    }

    public void dfs2(int i,int j,int n,int m,char[][] grid){
        if(i>=0&&i<n&&j>=0&&j<m){
            if(grid[i][j]=='1'){
                grid[i][j]='2';
                dfs2(i+1,j,n,m,grid);
                dfs2(i-1,j,n,m,grid);
                dfs2(i,j+1,n,m,grid);
                dfs2(i,j-1,n,m,grid);
            }
        }
    }



    public int allmax=0;

    public int largestIsland(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;

        boolean isAll = true;

        for(int i=0;i<n;i++){
            for (int j=0;j<m;j++){
                if(grid[i][j]==0){
                    isAll = false;
                    break;
                }
            }
        }
        if(isAll){
            return n*m;
        }


        for(int i=0;i<n;i++){
            for (int j=0;j<m;j++){
                if(grid[i][j]==1){
                    grid[i][j]=dfs3(i,j,n,m,grid);
                }
            }
        }

        for(int i=0;i<n;i++){
            for (int j=0;j<m;j++){
                if(grid[i][j]>0){
                    int num = grid[i][j];
                    dfs4(num,i,j,n,m,grid);
                }
            }
        }

        for(int i=0;i<n;i++){
            for (int j=0;j<m;j++){
                if(grid[i][j]==0){
                    allmax = Math.max(allmax,dfs5(i-1,j,n,m,grid)+dfs5(i+1,j,n,m,grid)+dfs5(i,j-1,n,m,grid)+dfs5(i,j+1,n,m,grid)+1);
                }
            }
        }

        return allmax;
    }


    public int dfs3(int i,int j,int n,int m,int[][] grid){
        if(i>=0&&i<n&&j>=0&&j<m){
            if(grid[i][j]==1){
                grid[i][j]=-1;
                return dfs3(i+1,j,n,m,grid)+dfs3(i-1,j,n,m,grid)+dfs3(i,j+1,n,m,grid)+dfs3(i,j-1,n,m,grid)+1;
            }
            else {
                return 0;
            }
        }
        return 0;
    }


    public void dfs4(int num,int i,int j,int n,int m,int[][] grid){
        if(i>=0&&i<n&&j>=0&&j<m){
            if(grid[i][j]==-1){
                grid[i][j]=num;
                dfs4(num,i+1,j,n,m,grid);
                dfs4(num,i-1,j,n,m,grid);
                dfs4(num,i,j+1,n,m,grid);
                dfs4(num,i,j-1,n,m,grid);
            }
        }
    }

    public int dfs5(int i,int j,int n,int m,int[][] grid){
        if(i>=0&&i<n&&j>=0&&j<m){
           return grid[i][j];
        }
        return 0;
    }


}





